Perturbing a deterministic $n$-dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms [Spielman and Teng, JACM 2004], as it reduces the condition number of the input to $O(n)$, and with it the complexity of many matrix algorithms. However, when deployed algorithmically, these perturbations are expensive due to the cost of generating and storing $n^2$ Gaussian random variables. We propose a perturbation that requires generating and storing $O(n)$ random numbers in $O(\log n)$ bits of precision, and reduces the condition number of any deterministic matrix to $O(n)$, matching Gaussian perturbations. Our result in particular implies a better complexity for the perturbed conjugate gradient algorithm, showing that we can solve an $n\times n$ linear system in linear space to within an arbitrarily small constant backward error using $O(n)$ matrix-vector products. In our construction, we introduce the concept of a pattern matrix, which is a dense deterministic matrix that maps all sparse vectors into dense vectors, and we combine it with a sparse perturbation whose entries are dependent and located in a non-uniform fashion. In order to analyze this construction, we develop new techniques for lower bounding the smallest singular value of a random matrix with dependent entries.

Genetic Algorithms (GAs) are known for their efficiency in solving combinatorial optimization problems, thanks to their ability to explore diverse solution spaces, handle various representations, exploit parallelism, preserve good solutions, adapt to changing dynamics, handle combinatorial diversity, and provide heuristic search. However, limitations such as premature convergence, lack of problem-specific knowledge, and randomness of crossover and mutation operators make GAs generally inefficient in finding an optimal solution. To address these limitations, this paper proposes a new metaheuristic algorithm called the Genetic Engineering Algorithm (GEA) that draws inspiration from genetic engineering concepts. GEA redesigns the traditional GA while incorporating new search methods to isolate, purify, insert, and express new genes based on existing ones, leading to the emergence of desired traits and the production of specific chromosomes based on the selected genes. Comparative evaluations against state-of-the-art algorithms on benchmark instances demonstrate the superior performance of GEA, showcasing its potential as an innovative and efficient solution for combinatorial optimization problems.

N-ary relational knowledge bases (KBs) represent knowledge with binary and beyond-binary relational facts. Especially, in an n-ary relational fact, the involved entities play different roles, e.g., the ternary relation PlayCharacterIn consists of three roles, ACTOR, CHARACTER and MOVIE. However, existing approaches are often directly extended from binary relational KBs, i.e., knowledge graphs, while missing the important semantic property of role. Therefore, we start from the role level, and propose a Role-Aware Modeling, RAM for short, for facts in n-ary relational KBs. RAM explores a latent space that contains basis vectors, and represents roles by linear combinations of these vectors. This way encourages semantically related roles to have close representations. RAM further introduces a pattern matrix that captures the compatibility between the role and all involved entities. To this end, it presents a multilinear scoring function to measure the plausibility of a fact composed by certain roles and entities. We show that RAM achieves both theoretical full expressiveness and computation efficiency, which also provides an elegant generalization for approaches in binary relational KBs. Experiments demonstrate that RAM outperforms representative baselines on both n-ary and binary relational datasets.